import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/15 16:28
 * @description 扔掉在s中不在t中的字符，然后在滑动窗口
 */
public class Solution2 {
    public static void main(String[] args) {
        Solution2 solution = new Solution2();
        solution.minWindow("ADOBECODEBANC", "ABC");
    }

    public String minWindow(String s, String t) {
        int m = s.length();
        int n = t.length();
        if (m < n) {
            return "";
        }
        //利用hash数组替代Map
        int[] hash = new int[128];
        char[] S = s.toCharArray();
        char[] T = t.toCharArray();
        int left = 0, right = 0, count = 0;
        int start = 0, end = 0, minLen = Integer.MAX_VALUE;
        //初始化t字符串中的字母，例如：t中a出现了2次，对应的hash[a]=-2
        for (int i = 0; i < n; i++) {
            hash[T[i]]--;
        }
        //滑动窗口
        while (right < m) {
            //右边界后移一位
            char c = S[right++];
            //将当前字母出现次数+1
            hash[c]++;
            //如果出现次数<=0，说明该字母是t中包含的字母，则将count+1
            if (hash[c] <= 0) count++;
            //如果count！=t字符串的长度，说明当前窗口中还未包含所有t中的字母，跳过循环，继续右移边界。
            if (count != n) continue;
            //如果count==tlen，尝试缩小左边界
            //hash[schars[left]>0，说明该字母不是t中出现的字母，可以移出窗口
            while (hash[S[left]] > 0) {
                hash[S[left++]]--;
            }
            //计算当前窗口的大小，并记录当前窗口的索引
            if (right - left < minLen) {
                start = left;
                end = right;
                minLen = right - left;
            }
            //将左窗口右移一位，目的是将一个t中有的字符移出窗口，来继续向下查找有没有更小的窗口
            count--;
            hash[S[left++]]--;
        }
        return s.substring(start, end);
    }
}
